#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=33 lang=cpp
 *
 * [33] 搜索旋转排序数组
 */

// @lc code=start
class Solution {
public:
    // 1 2 2 2 3 3 3 4
    int search(vector<int>& nums, int target) {
        int l = 0, u = nums.size();
        // [)
        while (l < u - 1) {
            int middle = (l + u) / 2;
            if (nums[middle] == target) {
                return middle;
            }
            else if (nums[middle] > target) {
                if (target < nums[l] && nums[middle] >= nums[l]) {
                    l = middle + 1;
                }
                else u = middle;
            }
            else {
                if (target >= nums[l] && nums[middle] < nums[l]) {
                    u = middle;
                }
                else l = middle + 1;
            }
        }
        if (l >= nums.size()) return -1;
        return nums[l] == target ? l : -1;   
    }

    
};
// @lc code=end

